package com.owen.springboot.smartparkingms.module.app.util;

import com.owen.springboot.smartparkingms.module.app.entity.ParkArea;
import com.owen.springboot.smartparkingms.module.app.entity.ParkStatus;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NearSpaceUtils {
    public static double MaxValue = 100000;

    public static String getNearSpace(List<ParkArea> parkArea , List<ParkStatus> parkStatuses){
        int vertex = 1;  //初始起点
        List<Map> list = new ArrayList();
        for(ParkArea p : parkArea){
            Map map = new HashMap();
            map.put("areaVex",vertex); // 记录每个区域的开始位置
            vertex = vertex + p.getRowNum() * p.getColumnNum();
            map.put("endVex", vertex-1); // 记录每个区域的结束位置
            list.add(map);
        }

        /**
         * 建立初始邻接矩阵
         */
        double[][] matrix = new double[vertex][vertex];
        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                matrix[i][j] = MaxValue; // 每个点初始设为不可达
            }
        }
        /**
         * 将各区域的车位与初始起点的距离映射到邻接矩阵
         */
        for(int i = 0;i < parkArea.size();i++){
            double spaceFarEntrance = parkArea.get(i).getSpaceFarEntrance(); //获取区域与起点的最近距离
            int rowNum = parkArea.get(i).getRowNum();  // 区域行数
            int colNum = parkArea.get(i).getColumnNum(); // 区域列数
            double rowSpace = parkArea.get(i).getRowSpace();  // 区域行距
            double colSpace = parkArea.get(i).getColumnSpace();  // 区域列距
            int areaVex = (int)list.get(i).get("areaVex"); // 区域起始位置
            System.out.println("row"+rowNum+" col"+colNum+" colspace"+colSpace);
            matrix[0][areaVex] = spaceFarEntrance;
            //int spaceNum = Math.toIntExact(parkArea.get(i).getPlace());
            for(int j = 1;j <= rowNum;j++){   // 按行循环
                int a = areaVex + (j-1) * colNum;  //每一行的开始位置
                for(int z = 1;z < colNum; z++){
                    matrix[a+z-1][a+z] = rowSpace;  //把每个位置与横向相邻位置的距离设为行距
                    System.out.println("test"+(a+z-1)+(a+z));
                }
                if(j % 2 == 0){ //偶数行
                    int b = a - colNum;
                    for(int n = 0;n< colNum; n++){
                        matrix[b+n][a+n] = colSpace;  // 把偶数行的位置与纵向相邻位置的距离设为列距
                        System.out.println("Test"+(b+n)+(a+n));
                    }
                }
            }
        }

//        int[] visited = new int[matrix.length];
//        for(int i = 0; i < parkStatuses.size(); i++){
//            if(parkStatuses.get(i).getStatus().equals("空位")){
//                visited[i+1] = 0;
//            }else {
//                visited[i+1] = 1;
//            }
//        }
//        for (int i = 0;i<visited.length;i++){
//            System.out.println(visited[i]);
//        }

        double[] shortest = dijstra(matrix , 0);
        double min = MaxValue;
        int index = -1;
        for(int i = 1; i< shortest.length;i++){
            if( parkStatuses.get(i-1).getStatus().equals("空位") && shortest[i] < min){
                min = shortest[i];
                index = i;
            }
        }
        System.out.println(index);
        return parkStatuses.get(index-1).getSpaceId();
    }

    public static double[] dijstra(double[][] matrix, int source) {
        //最短路径长度
        double[] shortest = new double[matrix.length];
        //判断该点的最短路径是否求出
        int[] visited = new int[matrix.length];
        //存储输出路径
//        String[] path = new String[matrix.length];

        //初始化输出路径
//        for (int i = 0; i < matrix.length; i++) {
//            path[i] = new String(source + "->" + i);
//        }

        //初始化源节点
        shortest[source] = 0;
        visited[source] = 1;

        for (int i = 1; i < matrix.length; i++) {
            double min = MaxValue;
            int index = -1;

            for (int j = 0; j < matrix.length; j++) {
                //已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
                System.out.println("visit"+j+" "+visited[j]+" : "+ matrix[source][j]);
                if (visited[j] == 0 && matrix[source][j] < min) {
                    min = matrix[source][j];
                    index = j;
                }
            }

            //更新最短路径
            shortest[index] = min;
            visited[index] = 1;

            //更新从index跳到其它节点的较短路径
            for (int m = 0; m < matrix.length; m++) {
                if (visited[m] == 0 && matrix[source][index] + matrix[index][m] < matrix[source][m]) {
                    matrix[source][m] = matrix[source][index] + matrix[index][m];
                    System.out.println("update:"+index+" "+m+" "+matrix[source][m]);
//                    path[m] = path[index] + "->" + m;
                }
            }

        }

        return shortest;

        //打印最短路径
//        for (int i = 0; i < matrix.length; i++) {
//            if (i != source) {
//                if (shortest[i] == MaxValue) {
//                    System.out.println(source + "到" + i + "不可达");
//                } else {
//                    System.out.println(source + "到" + i + "的最短路径为：" + path[i] + "，最短距离是：" + shortest[i]);
//                }
//            }
//        }
    }

    public static void main(String[] args) {
        Long log = new Long(10);
        System.out.println(Math.toIntExact(log));
    }
}

//class DijstraAlgorithm {
//    //不能设置为Integer.MAX_VALUE，否则两个Integer.MAX_VALUE相加会溢出导致出现负权
//
//
//    public static void main(String[] args) {
//        Scanner input = new Scanner(System.in);
//        System.out.println("请输入顶点数和边数:");
//        //顶点数
//        int vertex = input.nextInt();
//        //边数
//        int edge = input.nextInt();
//
//        int[][] matrix = new int[vertex][vertex];
//        //初始化邻接矩阵
//        for (int i = 0; i < vertex; i++) {
//            for (int j = 0; j < vertex; j++) {
//                matrix[i][j] = MaxValue;
//            }
//        }
//        for (int i = 0; i < edge; i++) {
//            System.out.println("请输入第" + (i + 1) + "条边与其权值:");
//            int source = input.nextInt();
//            int target = input.nextInt();
//            int weight = input.nextInt();
//            matrix[source][target] = weight;
//        }
//
//        //单源最短路径，源点
//        int source = input.nextInt();
//        //调用dijstra算法计算最短路径
//        dijstra(matrix, source);
//    }
//
//
//}
